package code;

import java.util.Arrays;

/**
 * @author xiaovcloud
 * @description:
 * @since 2021/8/16 20:07
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 4, 2, 7, 5, 19, 11, 33, 28};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) {
            return;
        }
        int pivot = arr[rightBound];
        int leftPtr = leftBound;
        int rightPtr = rightBound - 1;
        while (leftPtr <= rightPtr) {
            while (leftPtr <= rightPtr && arr[leftPtr] <= pivot) leftPtr++;
            while (leftPtr <= rightPtr && arr[rightPtr] > pivot) rightPtr--;
            if (leftPtr < rightPtr) swap(arr, leftPtr, rightPtr);
        }
        swap(arr, leftPtr, rightBound);
        if (leftPtr > leftBound + 1) sort(arr, leftBound, leftPtr - 1);
        if (rightPtr < rightBound - 1) sort(arr, rightPtr + 1, rightBound);
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
